This invention relates to decoding codewords in a high speed data transmission system, and more particularly to decoding codewords which have been encoded using a variable word length (VWL) coding scheme.
Variable word length coding is a coding technique often used for lossless data compression. In accordance with this technique, fixed-length data is converted into variable-length codewords according to the statistics of the data. In general, the lengths of the codewords are chosen so that shorter codewords are used to represent the more frequently occurring data and longer codewords are chosen to represent the less frequently occurring data. By properly assigning the variable-length codewords to the library of all possible source codewords, the averaged word length of the variable-length code is shorter than that of the original data and, therefore, data compression is achieved. Huffman code design is a procedure commonly used to construct a minimum redundant variable word length code for a known data statistic. Generally, the encoding process can be implemented by a table-lookup process using the input data to address the table. The codewords and word-lengths are stored as table contents and outputted sequentially, through a buffer, at a constant data rate onto the data channel. At the receiving end, however, the decoding process is more complicated. Due to the variable-length nature, each codeword has to be segmented from the received bit string before it can be decoded into a source symbol. Therefore, the design of a variable word length decoder is always more difficult than the design of a variable word length encoder.
There are several methods to decode a stream of variable word length codewords. The one most often used is called the tree-searching algorithm. A variable word length code can always be represented by a tree with codewords as leaves (also called terminal nodes). The decoding starts from the root of the code tree and is guided by the received bit string to follow one of two branches at each node. When a leaf is reached, the end of a codeword is detected and it is segmented from the remaining string. This type of decoder includes logic circuitry corresponding to the tree and control circuitry to traverse the code tree. This approach may be slow, especially for long codewords, since a bit-by-bit search through the code tree is required for each decoded symbol.
High-speed requirements are particularly critical for the transmission of digitized high definition television (HDTV) signals. In such a digital HDTV system, it is expected that the digital video signal can be coded using high compression techniques so that all the video information is transmitted over a single 155 Mb/sec broadband ISDN (BISDN) channel. Variable word length decoding is difficult to achieve at these speeds that permit a single variable word length decoder to handle all the video information. In particular, the high speed processing that is required in a variable word length decoder is difficult to achieve with low-cost very large scale integrated (VLSI) circuit technology such as 1.2 micron CMOS VLSI technology currently of interest.
Due to the difficulty of implementing high-speed variable word length decoders, there are several special variable word length codes designed for fast and inexpensive decoders. For example, a variable word length encoder with a length-indicating prefix is proposed by J. Cocke et al in U.S. Pat. No. 3,717,851 issued Oct. 24, 1972. In "Variable Word Length Coding for a High Data Rate DPCM Video Coder," Proc. of Picture Coding Symposium, 1986, pp. 54-56, M. E. Lukacs proposed a hardware architecture that is capable of fast decoding of specially designed variable word length codes. These approaches tradeoff coding efficiency with hardware speed.
A table-lookup based approach is an alternative to the bit-by-bit search operation. In a table-lookup based approach, such as disclosed in U.S. Pat. No. 3,675,212, issued on July 4, 1972 to J. Raviv et al, the received bit string is compared with the contents of a codeword table. The codeword table has an entry associated with each possible variable word length codeword that includes the decoded fixed-length word and the length of the variable length word. When the sequence of leading bits in an input register matches one of the entries in the codeword table, a codeword match is indicated. The input register is then shifted by the number of bits indicated by the code length entry, thereby making the next sequence of bits available for comparison with entries in the codeword table. Feedback to the input is required to inform the input register of the number bits to shift after each variable-length word is decoded. It is this time-consuming feedback around the processing elements of prior art variable-length decoders that has limited their use for high-speed applications.
An object of the present invention is to decode variable-length codewords by means of a feedforward only decoder architecture, which does not require the length of each decoded codeword to be fed back to the input of the decoder, thereby advantageously increasing the processing speed capabilities of the decoder.